package cn.itcast.com.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Created by 郭浩 on 2020/8/20 11:11
 */
public class MyTree<E extends Comparable<E>> {
    public class Node {
        E value;
        Node left;
        Node right;

        public Node(E value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public Node root;

    public void add(E e) {
        if (e == null) {
            throw new IllegalArgumentException("error e  null");
        }
        if (root == null) {
            root = new Node(e, null, null);
            return;
        }
        //第一步找到添加的位置
        //记录当前位置
        Node tag = root;
        //记录当前的父节点
        Node tagFather = null;
        int mid = 0;
        while (tag != null) {
            mid = e.compareTo(tag.value);
            if (mid > 0) {
                tagFather = tag;
                tag = tag.right;
            } else if (mid < 0) {
                tagFather = tag;
                tag = tag.left;
            } else {
                //代表数组中已经存在了要添加的内容
                return;
            }
        }
        //循环结束找到要添加的位置
        //tagfather街上tag
        //mid > 0 ? (tagFather.right = new Node(e,null,null) : tagFather.left = new Node(e,null, null);
        if (mid > 0) {
            tagFather.right = new Node(e, null, null);
        } else {
            tagFather.left = new Node(e, null, null);
        }
    }

    public boolean delete(E e) {
        if (e == null) {
            throw new IllegalArgumentException("IllegalArgumentException: null");
        }
        if (root == null) {
            throw new RuntimeException("IllegalArgumentException: tree is null");
        }
        //第一步找到添加的位置
        //记录当前位置
        Node tag = root;
        //记录当前的父节点
        Node tagFather = null;
        int mid = 0;
        while (tag != null) {
            mid = e.compareTo(tag.value);
            if (mid > 0) {
                tagFather = tag;
                tag = tag.right;
            } else if (mid < 0) {
                tagFather = tag;
                tag = tag.left;
            } else {
                //代表数组中已经存在了要添加的内容
                break;
            }
        }
        if (mid != 0) return false;
        //目前已经找到 结点为tag
        //找右最小
        //左右子树都存在
        if (tag.right != null && tag.left != null) {
            Node minNode = tag.right;
            Node minNodeFather = tag;
            //要找到右子树的最小值,也就是右子树最左边
            while (minNode.left != null) {
                minNodeFather = minNode;
                minNode = minNode.left;
            }
            //进行替换，将找到的右子树的最小值填充在删除的位置
            tag.value = minNode.value;
            //有可能还有右子树
            tag = minNode;
            tagFather = minNodeFather;
        }
        //若tag没有左子树 ch等于右结点，tag有左子树，等于左结点
        Node ch = tag.left != null ? tag.left : tag.right;

        //如果是
        if (tagFather == null) {
            root = ch;
        } else if (tagFather.left == tag) {
            tagFather.left = ch;
            //如果是单分支结构直接使用
        } else {
            tagFather.right = ch;
        }
        return true;
    }

    //查找结点是否存在
    public boolean contains(E e) {
        //常规检查
        if (e == null) {
            throw new IllegalArgumentException("IllegalArgumentException: null");
        }
        if (root == null) {
            throw new RuntimeException("IllegalArgumentException: tree is null");
        }
        //从根节点开始向下找
        Node tag = root;
        int mid = 0;

        //tag为空表示查到底了
        while (tag != null) {
            //根据compareTo方法比较大小,移动tag
            mid = e.compareTo(tag.value);
            if (mid > 0) {
                tag = tag.right;
            } else if (mid < 0) {
                tag = tag.left;
            } else {
                return true;
            }
        }
        return false;
    }

    //获得最小值
    public E min() {
        //常规检查
        if (root == null) {
            throw new RuntimeException("error root null");
        }
        //设置起点
        Node min = root;
        //因为是最小值，我们需要从左边开始找即可
        while (min.left != null) {
            min = min.left;
        }
        return min.value;
    }

    //获得最小值
    public E max() {
        //常规检查
        if (root == null) {
            throw new RuntimeException("error root null");
        }
        //设置初始的最大值，因为是最大值，所以我们要从右边找
        Node max = root;
        while (root.right != null) {
            max = max.right;
        }
        return max.value;
    }

    //清空树
    public void clear() {
        //因为是链表，将根结点置为null即可
        root = null;
    }

    //判空
    public boolean isEmpty() {
        return root == null;
    }

    //先序遍历
    public List<E> perOrder() {
        //存储数据的列表
        List<E> list = new ArrayList<E>();
        if (root == null) {
            throw new RuntimeException("error");
        }
        perOrder(root, list);
        return list;
    }

    //先序是根左右，先查询到的元素不一定第一时间能够访问，所以使用栈
    private void perOrder(Node root, List<E> list) {
        //创建一个栈,存放访问到的结点
        Stack<Node> stack = new Stack<>();
        //将初始根节点压栈
        stack.push(root);
        //初始有一个元素，不停的进站出站也至少有一个元素，直到遍历完树上的所有元素才会停止
        while (!stack.isEmpty()) {
            //初始的第一个结点就是根节点直接抛出，之后的每一次循环都是子树的根节点
            Node pop = stack.pop();
            //将这个结点存入到list
            list.add(pop.value);
            //将根节点的左右子树压入栈中
            //因为栈先进后出，所以左边的根节点后进入
            stack.push(pop.right);
            stack.push(pop.left);

        }
    }

    //中序遍历
    public List<E> inOrder() {
        List<E> list = new ArrayList<>();
        if (root == null) {
            throw new RuntimeException("tree is null");
        }
        inOrder(root, list);
        return list;
    }

    private void inOrder(Node root, List<E> list) {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        //因为是中序，根不是最先的，所以还要判断根是否是null
        while (!stack.isEmpty() || node != null) {
            //先左，不停的往左走
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            //找到最左边的值之后，让它成为node有可能是具有右子树的根节点，也有可能是叶结点
            node = stack.pop();
            //弹栈之后
            list.add(node.value);
            //根节点已经改变，会在下一次循环执行while
            node = node.right;
        }
    }

    //后序遍历
    public List<E> postOrder() {
        List<E> list = new ArrayList<>();
        if (root == null) {
            throw new RuntimeException("tree null");
        }
        postOrder(root, list);
        return list;
    }

    private void postOrder(Node root, List<E> list) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            //先序后序差别不大，使用头插法即可
            list.add(0, pop.value);

            stack.push(pop.left);
            stack.push(pop.right);
        }
    }

    //层级遍历
    public List<E> levelOrder() {
        List<E> list = new ArrayList<>();
        if (root == null) {
            throw new RuntimeException("null");
        }
        levelOrder(root, list);
        return list;
    }

    private void levelOrder(Node root, List<E> list) {
        //每一层排队，先进先出，出了之后将子树进队
        LinkedList<Node> queue = new LinkedList<>();
        //先将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            //出队
            Node poll = queue.poll();
            list.add(poll.value);
            if (poll.left != null)
                queue.offer(poll.left);
            if (poll.right != null)
                queue.offer(poll.right);
        }
    }

    //层级遍历
    public List<E> levelOrderReverse() {
        List<E> list = new ArrayList<>();
        if (root == null) {
            throw new RuntimeException("null");
        }
        levelOrderReverse(root, list);
        return list;
    }

    //反转
    private void levelOrderReverse(Node root, List<E> list) {
        //每一层排队，先进先出，出了之后将子树进队
        LinkedList<Node> queue = new LinkedList<>();
        //先将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            //出队
            Node poll = queue.poll();
            list.add(poll.value);
            if (poll.right != null)
                queue.offer(poll.right);
            if (poll.left != null)
                queue.offer(poll.left);
        }
    }

    //反转
    private void levelOrderReverseTest(Node root, List<E> list) {
        //每一层排队，先进先出，出了之后将子树进队
        LinkedList<Node> queue = new LinkedList<>();
        //先将根节点入队
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            //出队
            Node poll = queue.poll();
            for (int i1 = 0; i1 < i; i1++) {
                System.out.print("/");
                System.out.print("\\");
            }
            System.out.println(poll.value);
            if (poll.right != null)
                queue.offer(poll.right);
            if (poll.left != null)
                queue.offer(poll.left);
        }
    }

    public Node invertTree(Node root) {
        if (root == null) {
            return null;
        }
        //使用一个结点来暂时存储左子树
        Node temp = root.left;
        //将右边的子树挪到左边来，并进行镜像翻转
        root.left = invertTree(root.right);
        root.right = invertTree(temp);

        return root;

    }

    //获得高度
    public int height() {
        if (this.root == null) {
            throw new RuntimeException("null");
        }
        int height = height(root);
        return height;
    }

    private int height(Node root) {
        if (root == null) {
            return 0;
        }
        //递归
        int left = height(root.left) + 1;
        int right = height(root.right) + 1;
        return left > right ? left : right;
    }

    //创建树，通过中序和另外任意一个
    public MyTree<E> build(List<E> perOrder, List<E> inOrder) {
        MyTree<E> tree = new MyTree<>();
        tree.root = buildByOrder(perOrder, inOrder);
        return tree;
    }

    private Node buildByOrder(List<E> perOder, List<E> inOder) {
        if (perOder.size() == 0){
            return null;
        }

        //首先, 共先序的第一个元素, 获得根节点
        E value = perOder.get(0);

        //根据根节点, 查找根节点在中序序列的位置
        int index = inOder.indexOf(value);

        List<E> inOderLeft =  inOder.subList(0, index);
        List<E> inOderRight =  inOder.subList(index + 1, inOder.size());
        List<E> perOderLeft =  perOder.subList(1, index + 1);
        List<E> perOderRight =  perOder.subList(index + 1, perOder.size());

        Node node = new Node(value, null, null);
        node.left = buildByOrder(perOderLeft, inOderLeft);
        node.right = buildByOrder(perOderRight, inOderRight);

        return node;
    }

}





























































